package hot100;


/*
 * Author：江松
 * Date：2023/4/8 14:01
 *
 每日温度:
 1,暴力超时
 2，单调栈（自己想的版）:
 反向遍历，如果此时温度比后一天的低，说明最接近的就是后一天
 如果此时温度比后一天高，那么继续往前遍历，最接近的高温就是此时
 所以满足一个单调性，维护一个单调递减栈
 注意：后面元素使得当前元素弹出时，除了累加1次，还要加上当前元素弹出过的元素数
 同时要注意相等的情况


 3，题解：
 */

import java.util.HashMap;
import java.util.Stack;


public class Main739 {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stk = new Stack<>();
        int ans[] = new int[temperatures.length];
        //表示栈中元素弹出元素的数量
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = temperatures.length - 1; i >= 0; --i) {
            int n = temperatures[i];
            int t = 0;
            //表示在此之前已经丢掉的元素数量
            int out = 0;
            while (!stk.isEmpty() && n >= stk.peek()) {
                out += map.get(stk.peek());
                stk.pop();
                //本次丢掉的
                t++;
            }
            //本次丢掉的和之前丢掉的
            map.put(n, t + out);
            if (stk.isEmpty()) {
                ans[i] = 0;
            } else {
                ans[i] = map.get(n)+1;
            }
            stk.push(n);
        }
        return ans;
    }
}
